/* 实现思路:
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果被扫描的元素（已排序）大于新元素，将该元素后移一位
重复步骤3(可以使用while)，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
*/
function insertSort (arr) {
  if (!Array.isArray(arr)) {
    return false
  }
  if (arr.length <= 1) {
    return arr
  }
  for (let i = 1; i < arr.length; i++) {
    let curValue = arr[i]
    let j = i - 1
    while (j >= 0 && curValue < arr[j]) {
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = curValue
  }
  return arr
}
let arr = [3, 2, 5, 4, 1, 6]
console.log(insertSort(arr))